<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>递归算法</title>
  </head>
  <body>
    <script>
      /*
       * 递归：在函数中自己调用自己；
       * 作用：凡是需要您构建或遍历树状数据结构的问题基本都可以通过递归来解决；
       * 递归的步骤:
       * 1.假设递归函数已经写好
       * 2.寻找递推关系
       * 3.将递推关系的结构转换为递归体
       * 4.将临界条件加入到递归体中
       */
      //经典案例 1：求和：假设有一个函数：从1加到n。例如，当n = 4，它实现的就是“1 + 2 + 3 + 4”。
      function Sum(n) {
        if (n == 1) {
          return 1;
        } else {
          return n + Sum(--n);
        }
      }
      Sum(4); // console.log(Sum(4))

      //经典案例 2： 斐波拉契数列: 1,1,2,3,5,8,13,21,34,55,89...求第 n 项
      function fib(n) {
        if (n == 1 || n == 2) {
          return n - 1;
        } else {
          return fib(n - 1) + fib(n - 2);
        }
      }
      fib(10); //console.log(fib(2))
    </script>
  </body>
</html>
